import { ComparisonResults, compare, swap } from "../00.工具/utils.js"

export default class MaxHeap {
    heap = []

    getLeftIndex(index) {
        return 2 * index + 1
    }

    getRightIndex(index) {
        return 2 * index + 2
    }

    getParentIndex(index) {
        return Math.floor((index - 1) / 2)
    }

    insert(value) {
        if (value != null) {
            this.heap.push(value)
            this.shiftUp(this.heap.length - 1)
            return true
        }
        return false
    }

    shiftUp(index) {
        let currentIndex = index
        let parentIndex = this.getParentIndex(index)

        while (currentIndex > 0 && compare(this.heap[currentIndex], this.heap[parentIndex]) === ComparisonResults.BIGGER) {
            swap(this.heap, currentIndex, parentIndex)
            currentIndex = parentIndex
            parentIndex = this.getParentIndex(currentIndex)
        }
    }

    size() {
        return this.heap.length
    }

    isEmpty() {
        return this.size() === 0
    }

    extract() {
        if (this.isEmpty()) {
            return null
        }
        if(this.size() === 1){
            return this.heap.pop()
        }
        const removed = this.heap[0]
        this.heap[0] = this.heap.pop()
        this.shiftDown(0)
        return removed

    }

    shiftDown(index) {
        let current = index
        const leftIndex = this.getLeftIndex(current)
        const rightIndex = this.getRightIndex(current)
        const heapSize = this.size()

        if (leftIndex <= heapSize && compare(this.heap[leftIndex], this.heap[current]) === ComparisonResults.BIGGER) {
            current = leftIndex
        }

        if (rightIndex <= heapSize && compare(this.heap[rightIndex], this.heap[current]) === ComparisonResults.BIGGER) {
            current = rightIndex
        }

        if (index !== current) {
            swap(this.heap, index, current)
            this.shiftDown(current)
        }
    }
}